{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "############From chap11 ML of DSScratch \n",
    "from collections import Counter\n",
    "import math, random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def split_data(data, prob):\n",
    "    \"\"\"split data into fractions [prob, 1 - prob]\"\"\"\n",
    "    results = [], []\n",
    "    for row in data:\n",
    "        results[0 if random.random() < prob else 1].append(row)\n",
    "    return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def train_test_split(x, y, test_pct):\n",
    "    data = list(zip(x, y))                        # pair corresponding values\n",
    "    train, test = split_data(data, 1 - test_pct)  # split the dataset of pairs\n",
    "    x_train, y_train = list(zip(*train))          # magical un-zip trick\n",
    "    x_test, y_test = list(zip(*test))\n",
    "    return x_train, x_test, y_train, y_test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def accuracy(tp, fp, fn, tn):\n",
    "    correct = tp + tn\n",
    "    total = tp + fp + fn + tn\n",
    "    return correct / total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.98114\n"
     ]
    }
   ],
   "source": [
    "print(accuracy(70, 4930, 13930, 981070))   # 0.98114"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def precision(tp, fp, fn, tn):\n",
    "    return tp / (tp + fp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.014\n"
     ]
    }
   ],
   "source": [
    "print(precision(70, 4930, 13930, 981070))   # 0.014"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def recall(tp, fp, fn, tn):\n",
    "    return tp / (tp + fn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.005\n"
     ]
    }
   ],
   "source": [
    "print(recall(70, 4930, 13930, 981070))  # 0.005"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f1_score(tp, fp, fn, tn):\n",
    "    p = precision(tp, fp, fn, tn)\n",
    "    r = recall(tp, fp, fn, tn)\n",
    "\n",
    "    return 2 * p * r / (p + r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "accuracy(70, 4930, 13930, 981070) 0.98114\n",
      "\n",
      "precision(70, 4930, 13930, 981070) 0.014\n",
      "\n",
      "recall(70, 4930, 13930, 981070) 0.005\n",
      "\n",
      "f1_score(70, 4930, 13930, 981070) 0.00736842105263158\n"
     ]
    }
   ],
   "source": [
    "print(\"accuracy(70, 4930, 13930, 981070)\", accuracy(70, 4930, 13930, 981070))\n",
    "print()\n",
    "print(\"precision(70, 4930, 13930, 981070)\", precision(70, 4930, 13930, 981070))\n",
    "print()\n",
    "print(\"recall(70, 4930, 13930, 981070)\", recall(70, 4930, 13930, 981070))\n",
    "print()\n",
    "print(\"f1_score(70, 4930, 13930, 981070)\", f1_score(70, 4930, 13930, 981070)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# -*- coding: iso-8859-15 -*-\n",
    "############From chap8 Gradience of DSScratch\n",
    "from collections import defaultdict, Counter\n",
    "#from linear_algebra import distance, vector_subtract, scalar_multiply\n",
    "from functools import partial, reduce\n",
    "import re, math, random\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "#\n",
    "# functions for working with vectors\n",
    "#\n",
    "\n",
    "def vector_add(v, w):\n",
    "    \"\"\"adds two vectors componentwise\"\"\"\n",
    "    return [v_i + w_i for v_i, w_i in zip(v,w)]\n",
    "\n",
    "def vector_subtract(v, w):\n",
    "    \"\"\"subtracts two vectors componentwise\"\"\"\n",
    "    return [v_i - w_i for v_i, w_i in zip(v,w)]\n",
    "\n",
    "def vector_sum(vectors):\n",
    "    return reduce(vector_add, vectors)\n",
    "\n",
    "def scalar_multiply(c, v):\n",
    "    return [c * v_i for v_i in v]\n",
    "\n",
    "def vector_mean(vectors):\n",
    "    \"\"\"compute the vector whose i-th element is the mean of the\n",
    "    i-th elements of the input vectors\"\"\"\n",
    "    n = len(vectors)\n",
    "    return scalar_multiply(1/n, vector_sum(vectors))\n",
    "\n",
    "def dot(v, w):\n",
    "    \"\"\"v_1 * w_1 + ... + v_n * w_n\"\"\"\n",
    "    return sum(v_i * w_i for v_i, w_i in zip(v, w))\n",
    "\n",
    "def sum_of_squares(v):\n",
    "    \"\"\"v_1 * v_1 + ... + v_n * v_n\"\"\"\n",
    "    return dot(v, v)\n",
    "\n",
    "def magnitude(v):\n",
    "    return math.sqrt(sum_of_squares(v))\n",
    "\n",
    "def squared_distance(v, w):\n",
    "    return sum_of_squares(vector_subtract(v, w))\n",
    "\n",
    "def distance(v, w):\n",
    "   return math.sqrt(squared_distance(v, w))\n",
    "\n",
    "#\n",
    "# functions for working with matrices\n",
    "#\n",
    "\n",
    "def shape(A):\n",
    "    num_rows = len(A)\n",
    "    num_cols = len(A[0]) if A else 0\n",
    "    return num_rows, num_cols\n",
    "\n",
    "def get_row(A, i):\n",
    "    return A[i]\n",
    "\n",
    "def get_column(A, j):\n",
    "    return [A_i[j] for A_i in A]\n",
    "\n",
    "def make_matrix(num_rows, num_cols, entry_fn):\n",
    "    \"\"\"returns a num_rows x num_cols matrix\n",
    "    whose (i,j)-th entry is entry_fn(i, j)\"\"\"\n",
    "    return [[entry_fn(i, j) for j in range(num_cols)]\n",
    "            for i in range(num_rows)]\n",
    "\n",
    "def is_diagonal(i, j):\n",
    "    \"\"\"1's on the 'diagonal', 0's everywhere else\"\"\"\n",
    "    return 1 if i == j else 0\n",
    "\n",
    "identity_matrix = make_matrix(5, 5, is_diagonal)\n",
    "\n",
    "#          user 0  1  2  3  4  5  6  7  8  9\n",
    "#\n",
    "friendships = [[0, 1, 1, 0, 0, 0, 0, 0, 0, 0], # user 0\n",
    "               [1, 0, 1, 1, 0, 0, 0, 0, 0, 0], # user 1\n",
    "               [1, 1, 0, 1, 0, 0, 0, 0, 0, 0], # user 2\n",
    "               [0, 1, 1, 0, 1, 0, 0, 0, 0, 0], # user 3\n",
    "               [0, 0, 0, 1, 0, 1, 0, 0, 0, 0], # user 4\n",
    "               [0, 0, 0, 0, 1, 0, 1, 1, 0, 0], # user 5\n",
    "               [0, 0, 0, 0, 0, 1, 0, 0, 1, 0], # user 6\n",
    "               [0, 0, 0, 0, 0, 1, 0, 0, 1, 0], # user 7\n",
    "               [0, 0, 0, 0, 0, 0, 1, 1, 0, 1], # user 8\n",
    "               [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]] # user 9\n",
    "\n",
    "#####\n",
    "# DELETE DOWN\n",
    "#\n",
    "\n",
    "\n",
    "def matrix_add(A, B):\n",
    "    if shape(A) != shape(B):\n",
    "        raise ArithmeticError(\"cannot add matrices with different shapes\")\n",
    "\n",
    "    num_rows, num_cols = shape(A)\n",
    "    def entry_fn(i, j): return A[i][j] + B[i][j]\n",
    "\n",
    "    return make_matrix(num_rows, num_cols, entry_fn)\n",
    "\n",
    "\n",
    "def make_graph_dot_product_as_vector_projection(plt):\n",
    "\n",
    "    v = [2, 1]\n",
    "    w = [math.sqrt(.25), math.sqrt(.75)]\n",
    "    c = dot(v, w)\n",
    "    vonw = scalar_multiply(c, w)\n",
    "    o = [0,0]\n",
    "\n",
    "    plt.arrow(0, 0, v[0], v[1],\n",
    "              width=0.002, head_width=.1, length_includes_head=True)\n",
    "    plt.annotate(\"v\", v, xytext=[v[0] + 0.1, v[1]])\n",
    "    plt.arrow(0 ,0, w[0], w[1],\n",
    "              width=0.002, head_width=.1, length_includes_head=True)\n",
    "    plt.annotate(\"w\", w, xytext=[w[0] - 0.1, w[1]])\n",
    "    plt.arrow(0, 0, vonw[0], vonw[1], length_includes_head=True)\n",
    "    plt.annotate(u\"(v•w)w\", vonw, xytext=[vonw[0] - 0.1, vonw[1] + 0.1])\n",
    "    plt.arrow(v[0], v[1], vonw[0] - v[0], vonw[1] - v[1],\n",
    "              linestyle='dotted', length_includes_head=True)\n",
    "    plt.scatter(*zip(v,w,o),marker='.')\n",
    "    plt.axis('equal')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_of_squares(v):\n",
    "    \"\"\"computes the sum of squared elements in v\"\"\"\n",
    "    return sum(v_i ** 2 for v_i in v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def difference_quotient(f, x, h):\n",
    "    return (f(x + h) - f(x)) / h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def plot_estimated_derivative():\n",
    "\n",
    "    def square(x):\n",
    "        return x * x\n",
    "\n",
    "    def derivative(x):\n",
    "        return 2 * x\n",
    "\n",
    "    derivative_estimate = lambda x: difference_quotient(square, x, h=0.00001)\n",
    "    #derivative_estimate = partial(difference_quotient, square, h=0.00001)\n",
    "\n",
    "    # plot to show they're basically the same\n",
    "    import matplotlib.pyplot as plt\n",
    "    x = range(-10,10)\n",
    "    plt.plot(x, map(derivative, x), 'rx')           # red  x\n",
    "    plt.plot(x, map(derivative_estimate, x), 'b+')  # blue +\n",
    "    plt.show()                                      # purple *, hopefully"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def partial_difference_quotient(f, v, i, h):\n",
    "\n",
    "    # add h to just the i-th element of v\n",
    "    w = [v_j + (h if j == i else 0)\n",
    "         for j, v_j in enumerate(v)]\n",
    "\n",
    "    return (f(w) - f(v)) / h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def estimate_gradient(f, v, h=0.00001):\n",
    "    return [partial_difference_quotient(f, v, i, h)\n",
    "            for i, _ in enumerate(v)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def step(v, direction, step_size):\n",
    "    \"\"\"move step_size in the direction from v\"\"\"\n",
    "    return [v_i + step_size * direction_i\n",
    "            for v_i, direction_i in zip(v, direction)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_of_squares_gradient(v):\n",
    "    return [2 * v_i for v_i in v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def safe(f):\n",
    "    \"\"\"define a new function that wraps f and return it\"\"\"\n",
    "    def safe_f(*args, **kwargs):\n",
    "        try:\n",
    "            return f(*args, **kwargs)\n",
    "        except:\n",
    "            return float('inf')         # this means \"infinity\" in Python\n",
    "    return safe_f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#\n",
    "#\n",
    "# minimize / maximize batch\n",
    "#\n",
    "#\n",
    "\n",
    "def minimize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):\n",
    "    \"\"\"use gradient descent to find theta that minimizes target function\"\"\"\n",
    "\n",
    "    step_sizes = [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]\n",
    "\n",
    "    theta = theta_0                           # set theta to initial value\n",
    "    target_fn = safe(target_fn)               # safe version of target_fn\n",
    "    value = target_fn(theta)                  # value we're minimizing\n",
    "\n",
    "    while True:\n",
    "        gradient = gradient_fn(theta)\n",
    "        next_thetas = [step(theta, gradient, -step_size)\n",
    "                       for step_size in step_sizes]\n",
    "\n",
    "        # choose the one that minimizes the error function\n",
    "        next_theta = min(next_thetas, key=target_fn)\n",
    "        next_value = target_fn(next_theta)\n",
    "\n",
    "        # stop if we're \"converging\"\n",
    "        if abs(value - next_value) < tolerance:\n",
    "            return theta\n",
    "        else:\n",
    "            theta, value = next_theta, next_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def negate(f):\n",
    "    \"\"\"return a function that for any input x returns -f(x)\"\"\"\n",
    "    return lambda *args, **kwargs: -f(*args, **kwargs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def negate_all(f):\n",
    "    \"\"\"the same when f returns a list of numbers\"\"\"\n",
    "    return lambda *args, **kwargs: [-y for y in f(*args, **kwargs)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def maximize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):\n",
    "    return minimize_batch(negate(target_fn),\n",
    "                          negate_all(gradient_fn),\n",
    "                          theta_0,\n",
    "                          tolerance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#\n",
    "# minimize / maximize stochastic\n",
    "#\n",
    "\n",
    "def in_random_order(data):\n",
    "    \"\"\"generator that returns the elements of data in random order\"\"\"\n",
    "    indexes = [i for i, _ in enumerate(data)]  # create a list of indexes\n",
    "    random.shuffle(indexes)                    # shuffle them\n",
    "    for i in indexes:                          # return the data in that order\n",
    "        yield data[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def minimize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):\n",
    "\n",
    "    data = list(zip(x, y))\n",
    "    theta = theta_0                             # initial guess\n",
    "    alpha = alpha_0                             # initial step size\n",
    "    min_theta, min_value = None, float(\"inf\")   # the minimum so far\n",
    "    iterations_with_no_improvement = 0\n",
    "\n",
    "    # if we ever go 100 iterations with no improvement, stop\n",
    "    while iterations_with_no_improvement < 100:\n",
    "        value = sum( target_fn(x_i, y_i, theta) for x_i, y_i in data )\n",
    "\n",
    "        if value < min_value:\n",
    "            # if we've found a new minimum, remember it\n",
    "            # and go back to the original step size\n",
    "            min_theta, min_value = theta, value\n",
    "            iterations_with_no_improvement = 0\n",
    "            alpha = alpha_0\n",
    "        else:\n",
    "            # otherwise we're not improving, so try shrinking the step size\n",
    "            iterations_with_no_improvement += 1\n",
    "            alpha *= 0.9\n",
    "\n",
    "        # and take a gradient step for each of the data points\n",
    "        for x_i, y_i in in_random_order(data):\n",
    "            gradient_i = gradient_fn(x_i, y_i, theta)\n",
    "            theta = vector_subtract(theta, scalar_multiply(alpha, gradient_i))\n",
    "\n",
    "    return min_theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def maximize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):\n",
    "    return minimize_stochastic(negate(target_fn),\n",
    "                               negate_all(gradient_fn),\n",
    "                               x, y, theta_0, alpha_0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "using the gradient\n",
      "minimum v [0.0, 4.887061237161061e-06, 8.1451020619351e-07]\n",
      "minimum value 2.4546794411755593e-11\n",
      "\n",
      "using minimize_batch\n",
      "minimum v [-0.0009304595970494407, -0.0009304595970494407, 0.0006646139978924582]\n",
      "minimum value 2.1732218896774115e-06\n"
     ]
    }
   ],
   "source": [
    "#if __name__ == \"__main__\":\n",
    "\n",
    "print(\"using the gradient\")\n",
    "\n",
    "v = [random.randint(-10,10) for i in range(3)]\n",
    "\n",
    "tolerance = 0.0000001\n",
    "\n",
    "while True:\n",
    "    #print v, sum_of_squares(v)\n",
    "    gradient = sum_of_squares_gradient(v)   # compute the gradient at v\n",
    "    next_v = step(v, gradient, -0.01)       # take a negative gradient step\n",
    "    if distance(next_v, v) < tolerance:     # stop if we're converging\n",
    "        break\n",
    "    v = next_v                              # continue if we're not\n",
    "\n",
    "print(\"minimum v\", v)\n",
    "print(\"minimum value\", sum_of_squares(v))\n",
    "print()\n",
    "\n",
    "\n",
    "print(\"using minimize_batch\")\n",
    "\n",
    "v = [random.randint(-10,10) for i in range(3)]\n",
    "\n",
    "v = minimize_batch(sum_of_squares, sum_of_squares_gradient, v)\n",
    "\n",
    "print(\"minimum v\", v)\n",
    "print(\"minimum value\", sum_of_squares(v))"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
